package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-14 18:00
 */
public class RollingDpBag {
    public static void main(String[] args) {

    }

    /**
     * 1.j代表容量为j2.dp[j]代表j容量下存放的最大值2.dp[j]=max(dp[j],dp[j-weight[i]]+value[i])3.dp[i]=0;4.第一层是物品，从上到下，第二层是容量，从左到右
     */
    public static void dpBag(int[]weight,int []value,int maxSize){
        int[]dp=new int[maxSize+1];
        for(int i=0;i< weight.length;++i){
            for(int j=maxSize;j>=weight[i];--j){
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }


    }
}
